package com.xhl.common.algorithm;

import lombok.extern.slf4j.Slf4j;

import java.util.Scanner;

/**
 * 最小公倍数 和 最大公约数
 * @Author CazCen
 * @Date 2021/12/5 15:51
 */
@Slf4j
public class LowestCommonMultiple {

    /**
     * 求最小公倍数：公式法
     * 两个数a,b的最小公倍数是a*b/最大公约数
     * 由于两个数的乘积等于这两个数的最大公约数与最小公倍数的积，即（a，b）× [a，b] = a × b
     * 所以，求两个数的最小公倍数，就可以先求出它们的最大公约数，然后用上述公式求出它们的最小公倍数。
     */



    /**
     * 求最大公约数：辗转相除法
     * 1\. a/b，令r为所得余数（0≤r<b） 若r=0，算法结束，a即为答案
     * 2\. 互换：置 a←b，b←r，并返回第一步
     * 3、规则：0和任何一个数之间的关系：这个数就是最大公约数，因为0可以整除任何数，结果都为0
     */

    /**
     * 求最大公约数 辗转相除法
     * @param a
     * @param b
     * @return  最大公约数
     */
    public static int zdgys(int a,int b){
        if(b == 0) {
            return a;
        }
        return zdgys(b, a % b);
    }


    /**
     * 求最小公倍数  公式: (a*b)/最大公约数
     *
     */
    public static int zxgbs(int a, int b){
        return (a * b) / zdgys(a, b);
    }


    public static void test(){

        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();

        log.info("{}和{}的最大公约数是:{}",a,b,zdgys(a, b));

        log.info("{}和{}的最小公倍数是:{}",a,b,zxgbs(a, b));

        scanner.close();

    }

    public static void test(int a, int b){

        log.info("{}和{}的最大公约数是:{}", a, b,zdgys(a, b));

        log.info("{}和{}的最小公倍数是:{}", a, b, zxgbs(a, b));

    }

}
